package java_1_12.dynamic_array;

import java.util.Arrays;

/**
 * 基于数组的顺序表
 */

public class DynamicArray {
    //存储元素还是在数组中存储，只是套了一层类，从类访问就不用管数组长度
    private int[] data;//定义整型数组
    private int size;//当前动态数组中实际存储元素个数
    public DynamicArray() {
        data=new int[10];//data初始化，默认开辟10长度大小
    }
    public DynamicArray(int capacity){//传容量
        data=new int[capacity];
    }
    /**
     * 1.数组尾部插入-val:待插入元素值
     * 1）判断数组是否满了，满了扩容（扩为原来的1倍）
     * 2）尾插
     */
    public void addLast(int val){
        if(size==data.length){
            grow();//数组满，扩容：私有方法
        }
        data[size]=val;
        size++;
    }
    /**
     * 2.头插-第一个元素空出来，元素必须从最后开始向后依次移动，保证不覆盖原先元素
     * @param val
     */
    public void addFirst(int val){
        if(size== data.length){
            grow();
        }
        for (int i = size-1; i >=0 ; i--) {
            data[i+1]=data[i];
        }
        data[0]=val;
        size++;
    }
    /**
     * 3.在任意位置插入
     * @param index
     * @param val
     */
    public void addIndex(int index,int val){
        if(size== data.length){
            grow();
        }
        //合法性判断
        if(index<0||index>size){
            System.out.println("add index illegal");
            return;
        }
        else{
            //空出index位置
            for (int i = size-1; i >=index; i--) {
                data[i+1]=data[i];
            }
            data[index]=val;
            size++;
        }
    }
    /**
     * 4.查找当前数组中元素val对应的下标index
     */
    public int getByVal(int val){
        for (int i = 0; i < size; i++) {
            if(data[i]==val){
                return i;
            }
        }
        return -1;
    }
    /**
     * 5.元素查找-当前数组是否有该元素
     * @param val
     * @return true or false
     */
    public boolean contains(int val){
        int index=getByVal(val);
        if(index==-1){
            return false;
        }
        return true;
    }
    /**
     * 6.根据索引取得相应元素
     */
    public int get(int index){
        if(index<0||index>=size){
            System.out.println("get index illegal");
            return -1;
        }
        return data[index];
    }
    /**
     * 7.根据索引修改元素
     */
    public int set(int index,int newVal){
        if(index<0||index>=size) {
            System.out.println("set index illegal");
            return -1;
        }
        int oldVal=data[index];
        data[index]=newVal;
        return oldVal;
    }
    /**
     * 8.删除指定位置元素
     */
    public void removeIndex(int index){
        if(index<0||index>=size){
            System.out.println("remove index illegal");
            return;
        }
        for (int i = index; i < size-1; i++) {
            data[i]=data[i+1];
        }
        size--;
        data[size]=0;
    }
    /**
     * 9.删除数组中第一个值为val的节点
     */
    public void removeOnce(int val){
        for (int i = 0; i < size; i++) {
            if(data[i]==val){
                removeIndex(i);
                return;
            }
        }
        System.out.println("元素val不存在");
    }
    /**
     * 10.删除数组中所有值为val的元素
     */
    public void removeValAll(int val){
        for (int i = 0; i < size; i++) {
            while(i!=size&&data[i]==val){
                removeIndex(i);
            }
        }
    }

    /**
     * 遍历打印数组
     * @return 向外部返回一个字符串
     */
    public String toString(){
        String ret="[";
        for (int i = 0; i < size; i++) {
            ret+=data[i];
            if(i!=size-1){
                ret+=",";
            }
        }
        ret+="]";
        return ret;
    }
    private void grow() {
        int[] newData= Arrays.copyOf(data,data.length<<1);
        this.data=newData;
    }
}
